package org.hmh.others.haoweilai;

import org.hmh.leetcode.dataStruct.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class exam1 {

    static public int getMax(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        int max = Integer.MIN_VALUE;
        int sum=0;
        TreeNode r = root;
        while (r!=null || !stack.empty()) {
            if (r != null) {
                stack.push(r);
                sum += r.val;
                r = r.left;
            }
            else {
                if (sum > max) {
                    max = sum;
                }
                r = stack.pop();
                sum -= sum-r.val;

                r = r.right;
            }
        }
        return max;
    }

    static public int getMax2(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<>();

        if (root == null) return 0;

        TreeNode p = root;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                sum += p.val;
                stack.push(p);
                p = p.left;
            } else {
                max = Math.max(max, sum);
                p = stack.pop();
                sum -= sum - p.val;
                p = p.right;
            }
        }
        max = Math.max(max, sum);
        return max;
    }

//    static int max = Integer.MIN_VALUE;
//    static public void dfs(TreeNode root,int sum) {
//        if (root == null) {
//            if(max<sum){
//                max = sum;
//            }
//            return;
//        }
//        dfs(root.left, sum + root.val);
//        dfs(root.right, sum + root.val);
//    }

    public static void main(String[] args){
        TreeNode treeNode = new TreeNode(25);
        treeNode.left = new TreeNode(1000);
        treeNode.right = new TreeNode(54);
        treeNode.left.left = new TreeNode(56);
        treeNode.right.right = new TreeNode(5000);
        System.out.println(getMax(treeNode));
    }
}
